package com.leet.bfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/*
* 关键点在于时刻更新*/
public class CloneGraph {
    private HashMap<Node,Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
         if( node == null )  return null;
         // 链表
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        visited.put(node, new Node(node.val,new ArrayList<>()));
        while(!queue.isEmpty()){
            Node front = queue.poll();
            // 一个front多次add neighbor
            for(Node neighbor:front.neighbors){
                // 没有被访问过，放在visited里(一样的东西)
                if(!visited.containsKey(neighbor)) {
                    // 构建新节点
                    visited.put(neighbor, new Node(neighbor.val,new ArrayList<>()));
                    // 邻结点（旧的）加入队列
                    queue.offer(neighbor);
                }
                // 更新节点（从旧节点中获得关系，加入新建的neighbor中)，每次加入新的节点的neighbor值
                visited.get(front).neighbors.add(visited.get(neighbor));
            }
        }
            return visited.get(node);
    }
}
